package exercises.leetcode;

/**
 * <a href="https://leetcode-cn.com/problems/permutation-in-string/">
 * 567. 字符串的排列</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。
 * <p>
 * 换句话说，s1 的排列之一是 s2 的 子串 。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：s1 = "ab" s2 = "eidbaooo"
 * 输出：true
 * 解释：s2 包含 s1 的排列之一 ("ba").
 * <p>
 * 示例 2：
 * <p>
 * 输入：s1= "ab" s2 = "eidboaoo"
 * 输出：false
 *  
 * <p>
 * 提示：
 * <p>
 * 1 <= s1.length, s2.length <= 104
 * s1 和 s2 仅包含小写字母
 *
 * @author or2
 * @date 2021年09月24日 时间: 20:09
 */
public class No567 {
    public boolean checkInclusion(String s1, String s2) {
        /*输入校验*/
        if (s2.length() < s1.length()) {
            return false;
        }
        /*初始化数据*/
        char[] pattern = s1.toCharArray();
        char[] text = s2.toCharArray();
        int patternLength = pattern.length;

        /*统计字母出现的频次*/
        short[] letter = new short[26];
        for (char c : pattern) letter[c - 'a']++;
        /*有哪些字母出现过*/
        int bitmap = 0;
        for (int i = 0; i < letter.length; i++)
            if (letter[i] > 0) bitmap |= 1 << i;

        /*滑动窗口初始化*/
        for (int i = 0; i < patternLength; i++) {
            int offset = text[i] - 'a';
            short freq = --letter[offset];
            if (freq == -1 || freq == 0)
                bitmap ^= 1 << offset;
        }
        /*判断是否满足题目条件*/
        if (bitmap == 0) return true;

        /*窗口滑动*/
        for (int i = patternLength; i < text.length; i++) {
            /*新加入一个字符*/
            int offset = text[i] - 'a';
            short freq = --letter[offset];
            if (freq == -1 || freq == 0)
                bitmap ^= 1 << offset;
            /*窗口同时移除一个字符*/
            offset = text[i - patternLength] - 'a';
            freq = ++letter[offset];
            if (freq == 1 || freq == 0)
                bitmap ^= 1 << offset;
            /*判断当前窗口是否满足条件*/
            if (bitmap == 0) return true;
        }

        return false;
    }

    /**
     * 没啥用
     * <p><span color="red">
     * 位运算直接算吧
     * </span>
     */
    public boolean checkInclusionWithBitArray(String s1, String s2) {
        /*节省位运算时间*/
        int[] letterBit = new int[26];
        for (int i = 0; i < letterBit.length; i++) {
            letterBit[i] = 1 << i;
        }
        /*输入校验*/
        if (s2.length() < s1.length()) {
            return false;
        }
        /*初始化数据*/
        char[] pattern = s1.toCharArray();
        char[] text = s2.toCharArray();
        int patternLength = pattern.length;

        /*统计字母出现的频次*/
        short[] letter = new short[26];
        for (char c : pattern) letter[c - 'a']++;
        /*有哪些字母出现过*/
        int bitmap = 0;
        for (int i = 0; i < letter.length; i++)
            if (letter[i] > 0) bitmap |= letterBit[i];

        /*滑动窗口初始化*/
        for (int i = 0; i < patternLength; i++) {
            int offset = text[i] - 'a';
            short freq = --letter[offset];
            if (freq == -1 || freq == 0)
                bitmap ^= letterBit[offset];
        }
        /*判断是否满足题目条件*/
        if (bitmap == 0) return true;

        /*窗口滑动*/
        for (int i = patternLength; i < text.length; i++) {
            /*新加入一个字符*/
            int offset = text[i] - 'a';
            short freq = --letter[offset];
            if (freq == -1 || freq == 0)
                bitmap ^= letterBit[offset];
            /*窗口同时移除一个字符*/
            offset = text[i - patternLength] - 'a';
            freq = ++letter[offset];
            if (freq == 1 || freq == 0)
                bitmap ^= letterBit[offset];
            /*判断当前窗口是否满足条件*/
            if (bitmap == 0) return true;
        }

        return false;
    }
}
